package likou.dtgh.beibao;

public class _879_2 {
    /**
     * @param n      人数
     * @param m      最小盈利数
     * @param group  需要的人数
     * @param profit 盈利数
     * @return
     */
    public int profitableSchemes(int n, int m, int[] group, int[] profit) {
        int mod = 1000000007, res = 0;
        int[][] dp = new int[n + 1][m + 1];
        dp[0][0] = 1;
        for (int i = 0; i < profit.length; i++) {
            int cost = group[i];
            int p = profit[i];
            for (int k = n - cost; k >= 0; k--) {
                int l = m - p;
                if (l < 0) l = 0;
                for (int j = l; j <= m; j++) {
                    if (dp[k][j] > 0) dp[k + cost][m] = (dp[k][j] + dp[k + cost][m]) % mod;
                }
                for (int j = l - 1; j >= 0; j--) {
                    if (dp[k][j] > 0) dp[k + cost][j + p] = (dp[k][j] + dp[k + cost][j + p]) % mod;
                }
            }
        }
        for (int[] ints : dp) {
            res = (res + ints[m]) % mod;
        }
        return res;
    }
}
